var oldVnode = [
    {key:1,value:1},
    {key:2,value:2},
    {key:3,value:3},
    {key:4,value:4},
    {key:5,value:5},
]
var newVnode = [
    {key:1, value:1},
    {key:4,value:4},
    {key:2,value:22},
    {key:6,value: 6},
    {key:7,value: 7},
    {key:5,value:55},
]
var oldLength = oldVnode.length -1
var newLength = newVnode.length - 1

function patch(){}

var i = 0;


while(i <= oldLength && i <= newLength){
    if((oldVnode[i].key === newVnode[i].key) && oldVnode[i].key !== undefined){
        oldVnode[i] = newVnode[i]
    }else{
        break
    }
    i ++
}

while(i <= oldLength && i <= newLength){
    if((oldVnode[oldLength].key === newVnode[newLength].key) && oldVnode[oldLength].key !== undefined){
        oldVnode[oldLength] = newVnode[newLength]
    }else{
        break
    }
    oldLength --
    newLength --
}


if(i > oldLength) {

} else if ( i > newLength){

}else{
    const s1 = i
    const s2 = i
    const keyToNewIndexMap = new Map()
    for(i = s2; i<= newLength; i++){
        if(newVnode[i].key !== null){
            keyToNewIndexMap.set(newVnode[i].key, i)
        }
    }

    var j;
    var patched = 0;
    var toBePatched = newLength - s2 + 1 // newVnode中待处理的节点数
    var newIndexToOldIndexMap = new Array(toBePatched).fill(0)
    var oldNeedDel = [] // oldVnode 中需要删除的节点
    var moved = false //是否有移动
    var maxNewIndex = 0 // 记录newIndex的最大值，如何后面产生的newIndex值小于前面产生的newIndex值，
    // 则newVnode发生了的移动
    // 遍历oldVnode未处理节点
    for(i=s1; i<=oldLength; i++){
        // newVnode未处理节点已经处理完； oldVnode中多余的直接删除即可
        if(patched > toBePatched){
            oldNeedDel.push(i)
            continue
        }
        // newVnode未处理节点 和 oldVnode未处理节点 是否有key相同 或者 type相同的节点
        var newIndex ;
        if(oldVnode[i].key !== null){
            newIndex = keyToNewIndexMap.get(oldVnode[i].key)
        }else{
            for(j=s2; j<=newLength;j++){
                if(isSameVnodeType(newVnode[j], oldVnode[i])){
                    newIndex = j
                    break
                }
            }
        }

        // 没有， 删除oldVnode当前对比节点
        if(newIndex === void 0 ){
            oldNeedDel.push(i)
        }else{
            // 有
            oldVnode[i] = newVnode[newIndex]
            if(newIndex > maxNewIndex){
                moved = true
            }else{
                maxNewIndex = newIndex
            }
            // 新节点在旧数组中的位置
            newIndexToOldIndexMap[newIndex - s2] = i + 1
            patched ++
        }
    }

    console.log("oldVnode 需要删除的节点" , oldNeedDel)
    console.log("需要更新的节点", newIndexToOldIndexMap)

    const increasingNewIndexSequence = moved
                  ? getSequence(newIndexToOldIndexMap)
                  : EMPTY_ARR;
    j = increasingNewIndexSequence.length - 1;
    // 从后往前遍历待处理newVnode
    for (let i = toBePatched - 1; i >= 0; i--) {
        var nextIndex = s2 + i
        var nextVnode = newVnode[nextIndex]
        const anchor = newVnode[nextIndex + 1] 
        if (newIndexToOldIndexMap[i] === 0) {
            oldVnode
        }
        else if (moved) {
            // move if:
            // There is no stable subsequence (e.g. a reverse)
            // OR current node is not among the stable sequence
            if (j < 0 || i !== increasingNewIndexSequence[j]) {
                move(nextChild, container, anchor, 2 /* REORDER */);
            }
            else {
                j--;
            }
        }
        
    }
}

console.log(oldVnode)
console.log(newVnode)


// 最长递增子序列
function getSequence(arr) {
    const p = arr.slice();
    const result = [0];
    let i, j, u, v, c;
    const len = arr.length;
    for (i = 0; i < len; i++) {
        const arrI = arr[i];
        if (arrI !== 0) {
            j = result[result.length - 1];
            if (arr[j] < arrI) {
                p[i] = j;
                result.push(i);
                continue;
            }
            u = 0;
            v = result.length - 1;
            while (u < v) {
                c = (u + v) >> 1;
                if (arr[result[c]] < arrI) {
                    u = c + 1;
                }
                else {
                    v = c;
                }
            }
            if (arrI < arr[result[u]]) {
                if (u > 0) {
                    p[i] = result[u - 1];
                }
                result[u] = i;
            }
        }
    }
    u = result.length;
    v = result[u - 1];
    while (u-- > 0) {
        result[u] = v;
        v = p[v];
    }
    return result;
}